package com.fw.algorithm.find;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 二分查找算法
 * 1. 切割中间值不断进行查找
 */
public class BinarySearch {


    public static void main(String[] args) {
     int[] arr = {1,22,32,100,23,21,100};
        System.out.println(binarySearch2(arr,0,arr.length -1,100));
    }

    /**
     *
     * @param arr  原始数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findVal 要查找的值
     * @return
     */
    public static int binarySearch(int[] arr,int left,int right,int findVal){
        if (left > right){
            return -1;
        }
        // 开始切割 得到中间值
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        // 开始查找
        /**
         * 1. 如果当前中间值比 要查找的数据小 就直接 向右递归
         * 2. 如果当前中间值比 要查找的数据大 就直接 向左递归
         */
        if (midVal < findVal){
            //向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        }else if (midVal > findVal){
            // 向左递归
            return binarySearch(arr, mid - 1, right, findVal);
        }else{
            return mid;
        }
    }


    /**
     *
     * @param arr  原始数组
     * @param left 左边索引
     * @param right 右边索引
     * @param findVal 要查找的值
     * @return
     */
    public static List<Integer> binarySearch2(int[] arr,int left,int right,int findVal){
        if (left > right){
            return Collections.emptyList();
        }
        // 开始切割 得到中间值
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        // 开始查找
        /**
         * 1. 如果当前中间值比 要查找的数据小 就直接 向右递归
         * 2. 如果当前中间值比 要查找的数据大 就直接 向左递归
         */
        if (midVal < findVal){
            //向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        }else if (midVal > findVal){
            // 向左递归
            return binarySearch2(arr, mid - 1, right, findVal);
        }else{
// * 思路分析
// * 1. 在找到 mid 索引值，不要马上返回
// * 2. 向 mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合 ArrayList
// * 3. 向 mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合 ArrayList
// * 4. 将 Arraylist 返回
            // 开始操作，如果找到之后进行比较
            List<Integer> list = new ArrayList<>();
            //return mid;
            int temp = mid -1;
            while (true){
                if (temp < 0){
                    break;
                }
                if (arr[temp] == findVal)
                    list.add(temp);
                temp --;
            }
            list.add(mid);
            temp = mid +1;
            while (true){
                if (temp > right){
                    break;
                }
                if (arr[temp] == findVal)
                list.add(temp);

                temp ++;
            }
            return list;
        }
    }



}
